NetNews Offline 2/NetNews Offline Volume 2.iso/news/comp/lang/c-part1/360

Internet Message Format | 1996-08-05 | 8.7 KB

Path: hecate.umd.edu!ram
From: [e-mail] (Ram Samudrala)
Newsgroups: comp.infosystems.www.misc,comp.lang.misc,comp.lang.perl.misc,comp.lang.c
Subject: Re: Perl vs. C (was Re: Unix or NT? Get a Mac!)
Followup-To: comp.infosystems.www.misc,comp.lang.misc,comp.lang.perl.misc,comp.lang.c
Date: 4 Jan 1996 19:57:43 GMT
Organization: The Centre for Advanced Research in Biotechnology
Message-ID: <4chbfn$[e-mail]>
References: <4cgfp9$[e-mail]> <4ch1a5$[e-mail]>
Reply-To: [e-mail]
NNTP-Posting-Host: iris3.carb.nist.gov
X-Newsreader: TIN [version 1.2 PL0]

GENUINE PROBLEM FROM THE ACM EAST CENTRAL REGIONAL PROGRAMMING CONTEST
INCLUDED HERE.

Paul Phillips ([e-mail]) wrote:

>ANY from the last regional competition.

This is the problem.  The regional contests are not on-line (first of
all, I'm sick and home, and so I can't search the www).  I have my
1992 East-Central regional contest book in front of me.  They give you
solutions.   Some of the solutions are only 50-100 lines in Pascal, so
if you were good, then it can't take you more than 10-15 minutes.  The
problems in the contest are more complicated than what I gave.  As I
said, some of the problems were solved in 5 minutes.  Some took two
hours.

>it's like trying to argue with a Jesus freak.

Funny.  It's how I feel.

>They give six problems and five hours -- and nobody has ever finished
>all six problems (at least that's what we were told, and nobody did at
>ours either.)

They must have dumbed it down then. <-: We had 8 problems in 5 hours,
we did 5 (almost 7---it's a sad story doing with our inexperience),
and the top two teams (we were 6/70) did do 6 problems.

>It would be trivial for even a modestly accomplished Perl programmer
>to finish them all in that time span (and no, I won't test for your
>benefit.  Believe it or don't.)

Then there's no validity for your comments.  Put up or shut up.

>You contrived an extremely short almost wholly algorithmic problem as
>a comparison -- means nothing.

I didn't contrive it---it was a practice problem for one such contest.
But I did dig up the problems.  The problem descriptions are over a
page.

All right.  I've decided to be dumb enough and type in a description.
Ignore any typos.  This is the SHORTEST (in terms of text) problem of
the set which I'm just picking without even reading it (well, now I
have).  This was one of the problems we did solve fast (it's fairly
simple).   All the other problems are similar in nature.  The Pascal
code for this is about 60 lines. Note that you will be tested on other
inputs besides the example one.

-- PROBLEM G --

PUMP UP THE VOLUME

A particular part of the world has recently been experiencing a sudden
and marked proliferation of pirate radio stations.  So much so, in
fact, that a group of concerned nations have asked for your assistance
pinpointing the source of the illegal transmissions.  The respective
governments have agreed to provide you with data from a set of mobile
tracking units, each capable of determining its distance from a radio
signal's point of broadcast.  Armed with the information from 3 of
these units, and a 2-dimensional map of the area, you are to write a
program which will determine the distance and the direction of the
particular transmitter from the nearest city in your area.

INPUT

The input will consist of a 2-dimensional map (using Cartesian
coordinates) followed by the # of pirate signals that must be located
and a corresponding # of pirate station datasets.

In the map, the data for each city will appear on a separate line.
The data for each city will consist of a 15-character name followed by
the city's x- and y-coordinates and a radius.  The x and y coordinates
give the city's geographical centre, while the radius gives the
distance from the centre of the city to the city limits (all cities
may be considered circular in this problem).  There will be no more
than 50 cities and the last city on the map will be located at the
origin (0.0, 0.0).

Following the map is a single integer (on a line y itself) which gives
the # of pirate station datasets that follow.  Each pirate station
dataset will consist of nine readings on a single line, separated by
spaces.  The first three readings corresponding to mobile tracking
unit A, the next three to unit B, and the last three to unit C.  The
first 2 readings in a set of 3 are the x and y coordinates where the
mobile tracking unit itself is located while the third reading is the
distance the unit determined itself to be from the source of the
pirate radio station signal.  Note that all coordinates and distance
values are given in kilometeres and should be stored as real #s.  The
locations of the 3 mobile tracking units reporting information on the
irate signal will not be collinear and will always be at least 10
kilometres apart.  No city will be located more than 6000 kilometres
away from the city at the origin.  You may assume only valid data will
be supplied.

OUTPUT

Your program should process each pirate station dataset using the
information supplied bye he 3 mobile tracking units and produce a
summary line for each pirate signal which relates the source of the
broadcast to the nearest town on the map.  Specifically your output
should supply the distance from the illegal transmitter to the city
limits (not the geographical centre) of the nearest cit, the principle
compass direction of the illegal transmitter from the nearest city
(North, North East, East, South East, South, South West, West, or North
West), and the name of that city.

The distance should be correct within +- 0.02 of a kilometre and
output to two digits of accuracy.  To determine the compass direction
of the pirate transmitter from the nearest city, each of the eight
principle directions should be considered to be at a centre of a 45
degree arc in that direction.  Illegal transmitters which fall
anywhere within a a particular arc are considered to be in that
direction.  Thus if due north is at 0 degrees, a transmitter that was
at an angle between 22 degrees and 67 degrees (inclusive) would be
considered north east of the city while a transmitter that was at an
angle between 68 degrees and 112 degrees (inclusive) would be
considered east of the city.  When determining the direction of the
pirate transmitter, an angle should be rounded off the nearest whole
degree.

Pirate transmitters that are located inside a city;s limits should be
reported as originating from that city (no distance or directional
information should be output in this case). All pirate transmitter
reports should be preceded by a transmitter ID # (starting with
transmitter 1).  Refer to the following example for the acceptable
phrasing of your output.


EXAMPLE

Suppose the input file consisted of the following map and mobile
tracking unit readings:

--

Pleasantville   937.8      1277.34   4.9
Avion           494.17    -483.06    12.7
Caniama        -803.24     1351.68   6.53
Kingstons Falls-554.45    -300.0     1.82
Otisburg        0.0       0.0        3.6
5
286.91 1538.6 676.989 1627.84 1450.3 1026.29 1140.4 451.47 705.152
-1021.9 -1064.67 2164.66 1089.23 0.0 1796.91 993.94 -1516.17 2882.78
200.0 -295.6 824.776 -683.94 -1118.64 998.19 474.16 1729.8 2145.37
-173.21 -700.2 695.308 -202.87 191.04 971.421 1407.9 525.65 1369.38
747.02 419.61 628.79 0.0 -582.19 645.469 -987.65 294.3 1300.12

--

According to the above dataset, the town of Caniama is located at
(-803.24, 1351.68) and has a radius of 6.53 kilometres and there are 5
pirate transmitters in the pirate station dataset.  Furthermore, in
the case of pirate station #2, the mobile tracking units are reporting
the following information: mobile tracking unit A, which is located at
(-1021.9, -1064.67), has detected the transmission from 2164.66
kilometres away; Unit B located at (1089.23, 0.0) is receiving the
broadcast from 1796.91 kilometres away; and Unit C, located at
(993.94, -1516.17) , is picking it up from 2882.78 kilometres away.

Your program would generate the following output for this data:

Pirate Transmitter 1 is located 354.65 kilometres South West of Pleasantville
Pirate Transmitter 2 is located 524.55 kilometres South East of Caniama
Pirate Transmitter 3 is located 182.27 kilometres North of Kingstons Falls
Pirate Transmitter 4 is located in Avion
Pirate Transmitter 5 is located 275.12 kilometres East of Otisburg.

--

All right, there is it. Remember, output has to be exactly as
specified.

--Ram

[e-mail]  ||  http://www.ram.org  ||  http://www.twisted-helices.com/th
    If you didn't care what happened to me, and I didn't care for you,
    we would zig zag our way through the boredom and pain occasionally
  glancing up through the rain wondering which of the buggers to blame
  and watching for pigs on the wing.                     ---Pink Floyd